package queue

import "runtime"

//队列

type Queue struct {
	data  []interface{}
	front int
	rear  int
}

func NewQueue(maxSize int) *Queue {
	return &Queue{
		data:  make([]interface{}, maxSize),
		front: 0,
		rear:  0,
	}
}

func (q *Queue) Length() int { //返回长度
	return (q.rear - q.front + len(q.data)) / len(q.data)
}

//插入
func (q *Queue) Push(item interface{}) error {
	if (q.rear+1)%len(q.data) == q.front {
		return queuePullErr
	}

	q.data[q.rear] = item
	q.rear = (q.rear + 1) % len(q.data)
	return nil

}

//弹出
func (q *Queue) Pop() (interface{}, error) {
	if q.rear == q.front {
		return nil, queueEmptyErr
	}

	data := q.data[q.front]

	q.front = (q.front + 1) % len(q.data)

	return data, nil

}

//清空
func (q *Queue) Clear() {
	q.front = 0
	q.rear = 0
}

func (q *Queue) Empty() bool {
	return q.front == q.rear
}

//链队列

type Node struct {
	data interface{}
	next *Node
}

type LinkQueue struct {
	front *Node
	rear  *Node
	len   int
}

//根据切片生成队列
func NewLinkQueueBySlice(data []interface{}) *LinkQueue {
	q := NewLinkQueue()

	for _, item := range data {
		q.Push(item)
	}

	return q

}

func NewLinkQueue() *LinkQueue {
	return &LinkQueue{
		front: nil,
		rear:  nil,
		len:   0,
	}
}

func (l *LinkQueue) Push(item interface{}) {
	da := Node{
		data: item,
		next: nil,
	}

	if l.rear == nil && l.front == nil { //插入第一个
		l.rear = &da
		l.front = &da
		l.len++
		return
	}

	l.rear.next = &da //插入尾节点
	l.rear = &da      //跟新尾节点
	l.len++

}

//弹出
func (l *LinkQueue) Pop() (interface{}, error) {
	if l.front == nil {
		return nil, queueEmptyErr
	}

	data := l.front.data

	l.front = l.front.next
	if l.front == nil { //最后一个节点
		l.rear = nil
	}

	l.len--

	return data, nil

}

func (l *LinkQueue) Length() int {
	return l.len
}

//清空
func (l *LinkQueue) Clear() {
	l.len = 0
	l.front = nil
	l.rear = nil
	runtime.GC()
}

func (l *LinkQueue) Empty() bool {
	return l.front == nil
}

func (l *LinkQueue) GetTop() (interface{}, error) {
	if l.front == nil {
		return nil, queueEmptyErr
	}

	return l.front.data, nil

}
